package com.javaDemo.ti;

import java.util.Arrays;

/**
 * 排序算法示例类
 * 包含了常见的排序算法实现，每个算法都附带详细的中文注释说明
 * 包括算法原理、执行步骤、复杂度分析和适用场景等
 */
public class SortingAlgorithms {

    public static void main(String[] args) {
        // 测试数组
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        System.out.println("原始数组: " + Arrays.toString(arr));

        // 测试各种排序算法
        int[] arr1 = arr.clone();
        bubbleSort(arr1);
        System.out.println("冒泡排序后: " + Arrays.toString(arr1));

        int[] arr2 = arr.clone();
        selectionSort(arr2);
        System.out.println("选择排序后: " + Arrays.toString(arr2));

        int[] arr3 = arr.clone();
        insertionSort(arr3);
        System.out.println("插入排序后: " + Arrays.toString(arr3));

        int[] arr4 = arr.clone();
        quickSort(arr4, 0, arr4.length - 1);
        System.out.println("快速排序后: " + Arrays.toString(arr4));

        int[] arr5 = arr.clone();
        mergeSort(arr5, 0, arr5.length - 1);
        System.out.println("归并排序后: " + Arrays.toString(arr5));

        int[] arr6 = arr.clone();
        heapSort(arr6);
        System.out.println("堆排序后: " + Arrays.toString(arr6));
    }

    /**
     * 冒泡排序
     * 
     * 算法原理：
     * 就像气泡从水底升到水面一样，较大的元素会经过交换慢慢"浮"到序列的后端
     * 
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * 
     * 算法思想：
     * 1. 比较相邻的元素，如果第一个比第二个大，就交换它们
     * 2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对
     * 3. 针对所有的元素重复以上的步骤，除了最后一个
     * 4. 重复步骤1~3，直到没有任何一对数字需要比较
     * 
     * 图解示例：
     * 初始数组：[5, 3, 8, 4, 2]
     * 第一轮：
     * [3, 5, 8, 4, 2] -> [3, 5, 8, 4, 2] -> [3, 5, 4, 8, 2] -> [3, 5, 4, 2, 8]
     * 第二轮：
     * [3, 5, 4, 2, 8] -> [3, 4, 5, 2, 8] -> [3, 4, 2, 5, 8]
     * 第三轮：
     * [3, 4, 2, 5, 8] -> [3, 2, 4, 5, 8]
     * 第四轮：
     * [2, 3, 4, 5, 8]
     * 
     * 适用场景：
     * 1. 小规模数据排序
     * 2. 对稳定性有要求的场景
     * 3. 数据基本有序的情况
     */
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        // 外层循环控制排序轮数
        for (int i = 0; i < n - 1; i++) {
            // 内层循环控制每轮比较次数
            for (int j = 0; j < n - 1 - i; j++) {
                // 如果前一个元素大于后一个元素，则交换
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 选择排序
     * 
     * 算法原理：
     * 每次从未排序区间选择最小的元素，放到已排序区间的末尾
     * 
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * 
     * 算法思想：
     * 1. 在未排序序列中找到最小元素，存放到排序序列的起始位置
     * 2. 从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾
     * 3. 重复第二步，直到所有元素均排序完毕
     * 
     * 图解示例：
     * 初始数组：[64, 25, 12, 22, 11]
     * 第一轮：找到最小值11，与第一个元素交换
     * [11, 25, 12, 22, 64]
     * 第二轮：找到最小值12，与第二个元素交换
     * [11, 12, 25, 22, 64]
     * 第三轮：找到最小值22，与第三个元素交换
     * [11, 12, 22, 25, 64]
     * 
     * 适用场景：
     * 1. 数据规模较小
     * 2. 对空间复杂度要求高的场景
     * 3. 比较操作比交换操作更耗时的场景
     */
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        // 外层循环控制已排序序列的边界
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            // 内层循环寻找最小值
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            // 将找到的最小值和边界处的值交换
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

    /**
     * 插入排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * 
     * 算法思想：
     * 1. 从第一个元素开始，该元素可以认为已经被排序
     * 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
     * 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
     * 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
     * 5. 将新元素插入到该位置后
     * 6. 重复步骤2~5，直到所有元素均排序完毕
     */
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // 将比key大的元素都向后移动一位
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    /**
     * 快速排序
     * 时间复杂度：平均O(nlogn)，最坏O(n^2)
     * 空间复杂度：O(logn)
     * 稳定性：不稳定
     * 
     * 算法思想：
     * 1. 选择一个基准值（pivot），通常选择第一个或最后一个元素
     * 2. 将数组分为两部分，左边部分的值都小于基准值，右边部分的值都大于基准值
     * 3. 对左右两部分递归执行步骤1-2，直到数组完全排序
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 获取分区点
            int pi = partition(arr, low, high);

            // 递归排序左右两部分
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    // 快速排序的分区函数
    private static int partition(int[] arr, int low, int high) {
        // 选择最右边的元素作为基准值
        int pivot = arr[high];
        int i = (low - 1);

        // 将小于基准值的元素移到左边
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 将基准值放到正确的位置
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    /**
     * 归并排序
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(n)
     * 稳定性：稳定
     * 
     * 算法思想：
     * 1. 将数组分成两半，分别对两半进行排序
     * 2. 将排序好的两半合并成一个有序数组
     * 3. 递归执行步骤1-2，直到子数组的大小为1
     */
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            // 递归排序左右两半
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // 合并两个有序数组
            merge(arr, left, mid, right);
        }
    }

    // 归并排序的合并函数
    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // 创建临时数组
        int[] L = new int[n1];
        int[] R = new int[n2];

        // 将数据复制到临时数组
        for (int i = 0; i < n1; ++i)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[mid + 1 + j];

        // 合并临时数组
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // 复制剩余元素
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    /**
     * 堆排序
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * 
     * 算法思想：
     * 1. 将待排序序列构建成一个大顶堆
     * 2. 将堆顶元素与末尾元素交换，将最大元素沉到数组末端
     * 3. 重新调整结构，使其满足堆定义，继续交换堆顶元素与当前末尾元素
     * 4. 反复执行步骤2-3，直到整个序列有序
     */
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // 一个个从堆顶取出元素
        for (int i = n - 1; i > 0; i--) {
            // 将堆顶元素（最大值）与末尾元素交换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 对剩余元素重新构建大顶堆
            heapify(arr, i, 0);
        }
    }

    // 堆排序的堆调整函数
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        // 如果左子节点大于根节点
        if (left < n && arr[left] > arr[largest])
            largest = left;

        // 如果右子节点大于最大值
        if (right < n && arr[right] > arr[largest])
            largest = right;

        // 如果最大值不是根节点
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // 递归调整受影响的子树
            heapify(arr, n, largest);
        }
    }
}